A hash table, or hash map, is a data structure that uses a hash function to map identifying values, known as keys, to their associated values. For example, a key may include a name and the associated value may include their e-mail address. In this manner, a hash table implements an associative array. The hash function is used to transform the key into the index, or the hash, of an array element, often referred to as a slot or bucket, where the corresponding value is to be sought. For example, a hash function can calculate an index from the key of a data item and use the index to place the data into the array. In this respect, a hash function can be expressed asindex=f(key, ArrayLength)where ArrayLength is the size of the array. In many situations, hash tables turn out to be more efficient than search trees or any other table lookup structure. For this reason, they are widely used in many kinds of computer software, particularly for associative arrays, database indexing, caches, and sets.
In theory, the hash function could map each possible key to a unique slot index, but this ideal is rarely achievable in practice unless the hash keys are fixed, i.e., new entries are not added to the table after it is created. Instead, many hash table designs assume that hash collisions—different keys that map to the same hash value—will occur and be accommodated in some way. For example, if twenty-five hundred keys are hashed into a million array elements with uniform random distribution, the birthday paradox indicates that there will be approximately a ninety-five percent chance of at least two of the keys being hashed into the same array element. Developers continue to design hash functions to improve efficiency and to avoid collisions, so hash functions can behave differently, but at times a hash function can include deficiencies that are difficult to detect.
Hash tables are often dynamically resized to efficiently use memory resources. In a well-dimensioned hash table, the average cost measured in number of instructions for each lookup is independent of the number of elements stored in the table. Many hash table designs also allow arbitrary insertions and deletions of key-value pairs, at constant average cost per operation. As the number of items in a table grows, more memory can be allocated to the table and new array elements are created. The existing items can be rehashed and mapped to new array elements. Some implementations can shrink the size of the table as items are removed in order to recover memory.